Computer systems are often interconnected into vast computer networks. The computer systems connected on such networks communicate with each other by sending information through their electronic connections. The networks can be organized into various types of topologies. FIG. 1 illustrates one such topology. A network 100 comprises several local area networks 101-102 that are connected to a routing system 103. The computer systems of each local area network are connected to the communications link 101a-102a. When a source computer system on a local area network sends information to a destination computer system on the same local area network, the source computer system prepares a packet that includes the address of the destination computer system and transmits the packet on the communications link. The other computer systems on that same local area network (i.e., connected to the communications link) read the packet that was transmitted. The destination computer system detects that its address is included in that packet, and it processes the packet accordingly. Because of geographic and speed considerations, local area networks typically only include a limited number of computer systems that are in close proximity. For example, a company with offices in several locations may have a local area network at each location. However, the users of the computer systems may need to send packets to one another regardless to which of local area networks the users' computer systems are connected.
To allow packets to be sent from one local area network to another local area network, routing systems have been developed. A routing system is typically a dedicated special-purpose computer system to which each local area network is connected. The routing system maintains a cross-reference between computer system addresses and the local area network to which each computer system is connected. The routing system monitors the packets sent on each local area network to detect (using the cross-reference) when a computer system on one local area network is sending a packet to a computer system on another local area network. When the routing system detects such a packet, it forwards that packet onto the communications link for the local area network to which the destination computer system is connected. In this way, the routing system interconnects each of the local area networks into an overall network. Similar routing techniques are used to interconnect networks other than local area networks. For example, such routing techniques can be used on wide area networks and on the Internet.
Many different protocols have been developed to allow two computer systems to exchange information. If two computer systems support the same protocol, then they can exchange information. Certain protocols have been tailored to support the exchange of certain types of information efficiently. For example, the Internet protocol ("IP") was specified by the Department of Defense to facilitate the exchange of information between geographically separated computer systems. The IP specifies a destination in a packet format that identifies source and destination computer systems for data to exchange, but does not specify the format of the data itself. Several additional protocols may be used in conjunction with the IP to specify the format of the data. Once such additional protocol is the transmission control protocol ("TCP"). The TCP further specifies sub-protocols, such as the hyper-text transmission protocol ("HTTP") and the file transfer protocol ("FTP"), which specify the format of the data of the packet.
FIG. 2 is a diagram illustrating a typical packet sent on a local area network. The packet includes a network routing header followed by protocol specific data. The network routing header may include the destination computer address, the source computer address, and the length of the packet. The protocol specific data includes identification of the protocol and in the case of the IP includes the IP destination address, the IP source address, and the length of the IP portion of the packet. The data portion of the packet contains the sub-protocol identification plus other data of the packet.
Conventional routing systems often use a caching mechanism to speed the routing of the packets. When a packet is received, the routing system accesses its cross-reference of the local area networks and determines to which local area network the packet is to be routed. The routing system then stores that routing information in a cache. When subsequent packets are received, the routing system checks its cache and if the routing information for the packet is in the cache, then the routing system forwards the packet in accordance with the information in the cache. Although such a caching technique can help speed the routing of packets, such caching techniques are not used by routing systems when packet filtering is applied.
Packet filtering is often applied by a network administrator to restrict the type and timing of packets that are sent over the network. For example, a network administrator may want to restrict packets that are generated by a computer game from being transmitted over the network during normal business hours. A packet for a computer game may be identifiable, for example, by a TCP destination address, that indicates which application on the computer system identified by the IP destination address that is to receive the packet. Thus, the network administrator would configure the routing system to not forward any such packets during normal business hours. Also, the network administrator may want to filter out packets based on their source and destination addresses. For example, a company CEO may only want to receive packets from certain source computer systems and not every computer system on the network. When filtering is applied in conventional routing systems, caching is disabled and the slower procedure of checking the cross-reference information and filtering information is used for every packet. Thus, the processing not only of such filtered packets is slowed, but also of all packets is slowed because the cache is disabled.